home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / aie8911.zip / SPECS.COL < prev    next >
Text File  |  1989-08-31  |  13KB  |  284 lines

  1. NOVEMBER EXPERT TOOLBOX
  2.  
  3. Note to editor:   <I> is used to mark the start of italics.
  4. <R> is used to mark the end of italics.  Do not leave these
  5. in the text.  For example, if I write
  6.  
  7.       the <I>halt<R> predicate
  8.  
  9. you would put
  10.  
  11.       the halt predicate
  12.  
  13. in the text with 'halt' in italics.
  14.  
  15. ------------- Column starts here   ---------------------------------
  16.  
  17.              EXECUTABLE SPECIFICATIONS
  18.  
  19. One of the big problems in software development is the Catch 22
  20. of system specifications.  On a project of any size it is
  21. necessary to write specs to guide the implementation.  In theory,
  22. the implementation follows the specs and the resulting system
  23. does what you want.
  24.  
  25. However, in practice you are never 100% sure that a system meets
  26. its specs.  There is also no way of knowing if the specs
  27. themselves are correct.  This is because correct specs are those
  28. for which a true implementation does what the user wants --
  29. something you can't test, since the system isn't implemented yet.
  30.  
  31. One way out of this dilemma is specification testing.  Put the
  32. specifications in an executable form, for example a rapid
  33. prototype, and run them to see if they do what you want.
  34. Executable specs have several advantages:
  35.  
  36. * You can spot bugs in the specs early on, when the cost of
  37.   fixing them is relatively small.
  38.  
  39. * End users can see if the system appears to meet their goals
  40.   before implementation starts.
  41.  
  42. * A new development or maintenance programmer can use the
  43.   executable specs to learn about the system.  Running a model
  44.   system gives you an overview that is hard to get by reading
  45.   a bunch of data flow diagrams.
  46.  
  47. However, executable specs also have drawbacks:
  48.  
  49. * The programming needed to make specs executable may not become
  50.   part of the final system.  This specification programming, for
  51.   example to develop a rapid prototype, is an extra up-front
  52.   cost, which may or may not be recovered by having fewer errors
  53.   in the final system.
  54.  
  55. * The programming language gobbledygook needed to make the specs
  56.   executable also clutters them up.  Instead of reading English
  57.   or looking at diagrams, you may have to read code.  It may be
  58.   hard to separate the particulars used to execute the specs
  59.   from the more abstract properties desired in the final system.
  60.  
  61. To provide the advantages of executable specs while minimizing
  62. the drawbacks -- which can not be entirely eliminated -- I have
  63. written a specification interpreter (SI) in Prolog.  Advantages of
  64. this approach are:
  65.  
  66. * Prolog code is semi-logical in nature.  In addition to
  67.   implementing executable specs, the code describes logical
  68.   properties of the system.  Programming details are less visible
  69.   in Prolog code, because Prolog handles many control and data
  70.   structure details automatically.
  71.  
  72. * The specification interpreter also executes system components
  73.   described in English, by analyzing the description and using
  74.   the information to construct a simulation.  This lets the SI
  75.   execute specs before the more exact and detailed Prolog has
  76.   been written, or when the user just wants a high-level view of
  77.   the system.
  78.  
  79. * The SI works on partially complete -- in fact very incomplete
  80.   -- specs, by generating and calling simulation code for the
  81.   missing parts of the system.  We exploit Prolog's tools for
  82.   code generation to help the analyst check out partially
  83.   complete specs.
  84.  
  85. SOME EXAMPLES
  86.  
  87. Before we bog ourselves down in implementation details, let's
  88. look at some examples, shown in Listing 1.  Each process in the
  89. target system is defined by a <I>stub<R>, and optionally also by
  90. Prolog code.  The stub contains some minimal information about
  91. the process:  its <I>purpose<R>, an English phrase describing
  92. what the process does, and its <I>call<R>, a term showing how the
  93. process is called.
  94.  
  95. When we execute a specification, the process requested directly
  96. by the user and each subprocess called during the resulting
  97. computation is executed using either Prolog or stub definitions.
  98. Processes defined in Prolog are generally executed in Prolog,
  99. while those defined by stubs are executed using stubs.  (The user
  100. may, however, use stubs instead of Prolog to obtain a detail-free
  101. view of an executing system.  For details, see the complete SI
  102. program on the AI Expert and Instant Recall BBSs -- (301)
  103. 983-8439 for Instant Recall).
  104.  
  105. Specification 1 is a very minimal specification for checking
  106. housing survey data.  The specification interpreter recognizes
  107. that the process is defined as a stub only, and that this stub
  108. describes an action, rather than a branch, loop or other
  109. specialized process.  Therefore the SI turns the <I>purpose<R> of
  110. the process over to an action simulator, which does all that can
  111. be done with so little information:  tell the user that the
  112. process would be done at this point when the system runs.
  113.  
  114. Now suppose the systems analyst works another minute or two on
  115. the housing specs, producing the more elaborate Specification 2.
  116. Here the top level process is defined by Prolog as well as a
  117. stub.  Using information in the subprocess stubs, this Prolog
  118. translates into
  119.  
  120.      If the data is collected for a record, put it in the sample.
  121.      Otherwise, write an error message.
  122.  
  123. Even if you don't write Prolog, you can read it with a few
  124. minute's practice; it's an uncluttered notation for expressing
  125. relations among the subprocesses -- and it executes in a Prolog
  126. interpreter.
  127.  
  128. Actually, we'll execute Specification 2 not in an ordinary Prolog
  129. interpreter, but an enhanced one, the specification interpreter,
  130. which looks for stubs as well as code.  When we do this, we get
  131. the second execution trace shown in Listing 1.  The increased
  132. detail of this trace reflects the increased detail of the second
  133. spec.  Notice also that the SI recognizes <I>data_collected_q<R>
  134. as a branch, and interprets its stub accordingly.
  135.  
  136. The third example shows a process defined only by a stub.
  137. However the <I>purpose<R> of this process describes a loop, and
  138. the specification interpreter executes a loop, simulating the
  139. process inside the loop.
  140.  
  141. THE EXTENDED INTERPRETER
  142.  
  143. Listing 2 shows the top level of the specification interpreter.
  144. The top level predicate <I>do_goal<R> is essentially just a
  145. simplified Prolog interpreter in Prolog.  In fact, if you left
  146. out the first 2 rules of <I>do_goal<R>, you would have left a
  147. very no-frills Prolog interpreter -- one with no <I>cut<R>s or
  148. <I>or<R>s in the rules.  (You can add these features with some
  149. additional rules for <I>do_body<R>.)
  150.  
  151. As an extended Prolog interpreter, <I>do_goal<R> has to recurse
  152. and backtrack.  <I>do_goal<R> recurses because <I>do_goal<R>
  153. calls <I>do_body<R> and <I>do_body<R> calls <I>do_goal<R>.
  154. <I>do_goal<R> backtracks because the Prolog rules which define it
  155. and its helper predicates backtrack.
  156.  
  157. What transforms <I>do_goal<R> from "Prolog in Prolog" into a
  158. specification interpreter is the first rule of <I>do_goal<R>.
  159. This says that if there is a stub matching a Prolog goal, and it
  160. is appropriate to use it, then interpret the stub, for example
  161. because there is no Prolog rule matching the goal.
  162.  
  163. The top level of the stub interpreter appears in Listing 3.  The
  164. stub interpreter looks at the <I>purpose<R> of the stub, an
  165. English sentence fragment, and decides what kind of process is
  166. described, e.g.  branch, loop, action, etc.  Then the stub
  167. interpreter calls a specialized helper procedure to interpret
  168. that kind of process.
  169.  
  170. Listing 4 shows you how loops are executed based on stub
  171. information.  This predicate (Prolog procedure) extracts the
  172. information it needs, such as the action inside the loop, from
  173. the English-language <I>purpose<R> in the stub.  Then it uses
  174. this information to synthesize the Prolog code needed to simulate
  175. the loop described in the stub.  For the stub from Specification
  176. 3 in Listing 1, the generated loop code is shown in Listing 5.
  177.  
  178. If you need to generate a little code at runtime, Listing 4 shows
  179. you how to do it in Prolog.  The general plan is
  180.  
  181. * get rid of any old code that might confuse the system, using the
  182.   built-in predicate <I>abolish<R>
  183.  
  184. * Use patterns to construct the new code
  185.  
  186. * Assert the code into the Prolog database
  187.  
  188. * Call the top level goal of the new code
  189.  
  190. There are a couple details to observe in doing this:
  191.  
  192. * You can put variables in your patterns.  If the variables stand
  193.   for program segments, you can define the value of those segment
  194.   variables before or after their owner patterns -- as long as
  195.   the segments are defined before you put the rules containing
  196.   them in the Prolog database.
  197.  
  198. * If you define patterns as I did, with terms of the form
  199.  
  200.   <variable> = <pattern>,
  201.  
  202.   it's a good idea to put parentheses around the pattern, to make
  203.   sure the '=' is performed after all operators in the pattern.
  204.  
  205. * If you define the rules of a predicate in their intended order
  206.   -- the sensible thing to do -- put them in the database with
  207.   the queuing predicate <I>assertz<R> rather than the stacking
  208.   predicates <I>asserta<R> or its synonym <I>assert<R>.  (Some
  209.   Prologs make <I>assert<R> a synonym of <I>asserta<R> and some
  210.   of <I>assertz<R>; I avoid it for this reason.)
  211.  
  212. LINGUISTICS FOR ENGINEERS
  213.  
  214. Many of the helper predicates of the stub interpreter use
  215. information from the English <I>purpose<R> in the stub.  The
  216. predicates that extract this information are in Listing 6.  We
  217. have used really hokey predicates to find the verb and object of
  218. the stub <I>purpose<R>.  We could get away with this because we
  219. require the user to write process descriptions as the predicate
  220. (in the grammatical sense) of a single English sentence.  This
  221. requirement still affords the analyst a lot of descriptive
  222. freedom, but limits the amount of linguistic processing needed
  223. for the spec interpreter.  It is important to limit linguistic
  224. requirements, so development effort can be directed to the more
  225. crucial area of simulating additional process classes (e.g.
  226. menus and file I/O) and data descriptions to the SI.
  227.  
  228. With the analyst restricted to sentence predicates, let's look at
  229. the questions we have to answer from the <I>purpose<R> of a stub:
  230.  
  231.   Does the stub describe a branch?  A loop?  Some other special
  232.   kind of process?  To find out, look up the verb in a list
  233.   process-classifying words.  Because we have limited the
  234.   literary creativity of the specification writer, the verb is
  235.   the first word in the <I>purpose<R>.
  236.  
  237.   Is the action performed on a single item or a loop?  To find
  238.   out, see if the head of the main noun phrase of the verb object
  239.   is plural.  This is the first noun phrase after the verb.
  240.  
  241. The specification interpreter also has to do transform the
  242. <I>purpose<R> into an action-completed message, to inform
  243. the use when a process in a loop has been performed.
  244. The code that does this is in Listing 7.  Again, from a
  245. linguistic standpoint the code is very incomplete.  It
  246. overgeneralizes regular verbs in forming the past tense
  247. of verbs, as a small child does.  The result is somewhat
  248. inelegant, but understandable and simple to implement.
  249.  
  250. The singular rule is the most obviously incomplete -- and
  251. for a reason.  While the rule fails to find the singular of
  252. mass nouns like <I>sand<R>, this failure is really a kind
  253. of conservatism built into the system.  For if a processed
  254. item is identified as plural, it is processed in a loop.
  255. By recognizing only unmistakable plurals (OK, I know it
  256. messes up words like <I>pants<R> -- fix it if it matters)
  257. the system simulates a loop only when there is strong evidence
  258. for one.
  259.  
  260. AN AI DEMO FOR ANALYSTS
  261.  
  262. This specification interpreter illustrates the potential for
  263. AI to help in the software production process.  It also
  264. illustrates how current AI tools -- in this case Prolog --
  265. make symbolic programming easy.  The whole program took
  266. less than 2 days, although I did start with some code
  267. from Instant Recall's Prolog Tools.
  268.  
  269. The specification interpreter also illustrates a particular
  270. design philosophy, which I will call the Schultheisz approach, in
  271. honor of our firm's business manager:  Wait and see if you really
  272. need something before investing in it.  It would be easy to
  273. improve the SI's natural language processing, but is that the
  274. most important improvement to make?  Instead of making every part
  275. of the system smart, build a minimal system and let the domain
  276. specialist tell you what should be improved.  His or her
  277. judgement is almost certainly better on this than that of an AI
  278. expert without domain expertise.  By starting with a minimal
  279. expert system and letting the domain expert guide development,
  280. effort goes where it most improves the system.
  281.  
  282.  
  283.  
  284.